Uno de los primeros problemas de optimización estudiado durante los años 30 fue el llamado problema de la dieta, que consiste en conseguir una dieta equilibrada con el menor coste posible.

Más concretamente, una persona debe ingerir ciertas cantidades mínimas de una serie de elementos nutritivos básicos, que se encuentran en varios alimentos. Conociendo cuál es la cantidad de cada elemento en cada unidad de cada uno de los alimentos y el coste de la unidad de cada alimento, se trata de minimizar el coste de la dieta pero cubriendo las necesidades nutritivas mínimas.

Uno de los primeros en ocuparse de este problema fue Georges J. Stigler, que utilizando un método heuristico, obtuvo una solución óptima con un coste anual de 39,93 dólares, en precios de 1939.

Años más tarde, en 1947, Jack Landerman resuelve el problema, utilizando el método del simplex, trabajando con 9 restricciones y 77 incógnitas. Su solución, obtenida con calculadoras de mesa utilizadas durante 120 jornadas de trabajo, tenía un coste de 39,69 dólares anuales por persona. Es decir, la solución heurística de Stigler difería de la real en tan sólo 24 céntimos.

Hoy en día es posible obtener de una manera mucho más rápida soluciones a este problema, como puedes comprobar tú mismo en la página:

http://www.crmpa.it/pmma/Programmazione%20Lineare/Esperimento01.htm

El problema del transporte

En este caso se plantea la distribución óptima de una serie de mercancías entre los distintos centros de producción y de consumo. Es decir, un cierto producto se elabora en varios centros y debe ser enviado a varios destinos. Conocido el coste del transporte entre cada centro de producción y cada centro de consumo, la cantidad obtenida en cada centro de producción y la necesaria en cada centro de consumo, debe minimizarse el coste total del transporte.

El holandés Koopmans, se planteó durante la segunda guerra mundial, el plan de embarques de la carga entre distintos puertos. En su artículo "Exchange ratios between cargos in various routes", publicado en 1942, describe el problema mediante un grafo (una red), cuyos vértices son los puertos y cuyos arcos tienen asociado el tonelaje fletado entre cada par de puertos.

En 1958 se aplicaron los métodos de la Programación Lineal a un problema concreto: el cálculo del plan óptimo de transporte de arena de construcción a las obras de edificación de la ciudad de Moscú. En este problema había 10 puntos de partida y 230 de llegada. El plan óptimo de transporte, calculado con el ordenador Strena en 10 días del mes de junio, rebajó un 11% los gastos respecto a los costes previstos.